package com.leetcode.string;

import java.util.Stack;

/**
 * @author Dennis Li
 * @date 2020/10/15 21:40
 */
public class RemoveDuplicateLetters_316 {
    public String removeDuplicateLetters(String s) {
        int[] count = new int[256];
        Stack<Character> stack = new Stack<>();
        boolean[] inStack = new boolean[256];
        char[] chars = s.toCharArray();

        for (char c : chars) {
            // 记录各个字符出现的次数
            count[c]++;
        }

        for (char c : chars) {
            count[c]--;

            if (inStack[c]) continue;

            // 保证栈的单调性
            while (!stack.isEmpty() && stack.peek() > c) {
                // 如果当吧前字符的数量唯一，那么直接退出循环，其位置已经固定
                if (count[stack.peek()] == 0)
                    break;
                // 前面的元素
                inStack[stack.pop()] = false;
            }

            stack.push(c);
            inStack[c] = true;
        }

        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        return sb.reverse().toString();
    }
}
